package wwl.lsf;

import java.util.ArrayList;
import java.util.List;

/**
 * @Title
 * @Author wangwenliang
 * @Date 2021/3/29
 * @Description
 */
public class 解数独 {

    static class Solution {

        public static void main(String[] args) {

            char[][] board =
                    {
                            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                            {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
                    };

            Solution solution = new Solution();
            solution.solveSudoku(board);
//            输出：[['5','3','4','6','7','8','9','1','2'],['6','7','2','1','9','5','3','4','8'],['1','9','8','3','4','2','5','6','7'],['8','5','9','7','6','1','4','2','3'],['4','2','6','8','5','3','7','9','1'],['7','1','3','9','2','4','8','5','6'],['9','6','1','5','3','7','2','8','4'],['2','8','7','4','1','9','6','3','5'],['3','4','5','2','8','6','1','7','9']]

        }

        private boolean[][] line = new boolean[9][9];
        private boolean[][] column = new boolean[9][9];
        private boolean[][][] block = new boolean[3][3][9];
        private boolean valid = false;
        private List<int[]> spaces = new ArrayList<int[]>();

        public void solveSudoku(char[][] board) {
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    if (board[i][j] == '.') {
                        spaces.add(new int[]{i, j});
                    } else {
                        int digit = board[i][j] - '0' - 1;
                        line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                    }
                }
            }

            dfs(board, 0);
        }

        public void dfs(char[][] board, int pos) {
            if (pos == spaces.size()) {
                valid = true;
                return;
            }

            int[] space = spaces.get(pos);
            int i = space[0], j = space[1];
            for (int digit = 0; digit < 9 && !valid; ++digit) {
                if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) {
                    line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                    board[i][j] = (char) (digit + '0' + 1);
                    dfs(board, pos + 1);
                    line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
                }
            }
        }
    }

    static class mySolution {

        private boolean[][] rowFlag = new boolean[9][9];

        private boolean[][] columnFlag = new boolean[9][9];

        private boolean[][][] gridFlag = new boolean[3][3][9];

        private List<int[]> spaces = new ArrayList<>();

        private boolean valid = false;


        public void sloveShudu(char[][] board) {

            //赋值
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] == '.') {
                        spaces.add(new int[]{i, j});
                    } else {
                        int digital = board[i][j] - '0' - 1;
                        rowFlag[i][digital] = columnFlag[j][digital] = gridFlag[i / 3][j / 3][digital] = true;
                    }
                }
            }

            recursion(board, 0);

        }

        public void recursion(char[][] board, int level) {

            if (level == spaces.size()) {
                valid = true;
                return;
            }

            for (int digital = 0; digital < 9 && !valid; digital++) {
                int[] ints = spaces.get(level);
                if (!rowFlag[ints[0]][digital] && !columnFlag[ints[1]][digital] && !gridFlag[ints[0] / 3][ints[1] / 3][digital]) {
                    rowFlag[ints[0]][digital] = columnFlag[ints[1]][digital] = gridFlag[ints[0] / 3][ints[1] / 3][digital] = true;
                    board[ints[0]][ints[1]] = (char) (digital + '0' + 1);
                    recursion(board, level + 1);
                    rowFlag[ints[0]][digital] = columnFlag[ints[1]][digital] = gridFlag[ints[0] / 3][ints[1] / 3][digital] = false;
                }

            }


        }

    }

    public static void main(String[] args) {
        char a = '1';
        System.out.println(a - '0');
        System.out.println(a + '0');
    }


    static class Solution2 {
        private int[] line = new int[9];
        private int[] column = new int[9];
        private int[][] block = new int[3][3];
        private boolean valid = false;
        private List<int[]> spaces = new ArrayList<int[]>();

        public void solveSudoku(char[][] board) {
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    if (board[i][j] == '.') {
                        spaces.add(new int[]{i, j});
                    } else {
                        int digit = board[i][j] - '0' - 1;
                        flip(i, j, digit);
                    }
                }
            }

            dfs(board, 0);
        }

        public void dfs(char[][] board, int pos) {
            if (pos == spaces.size()) {
                valid = true;
                return;
            }

            int[] space = spaces.get(pos);
            int i = space[0], j = space[1];
            int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
            for (; mask != 0 && !valid; mask &= (mask - 1)) {
                int digitMask = mask & (-mask);
                int digit = Integer.bitCount(digitMask - 1);
                flip(i, j, digit);
                board[i][j] = (char) (digit + '0' + 1);
                dfs(board, pos + 1);
                flip(i, j, digit);
            }
        }

        public void flip(int i, int j, int digit) {
            line[i] ^= (1 << digit);
            column[j] ^= (1 << digit);
            block[i / 3][j / 3] ^= (1 << digit);
        }
    }
}

